1. Memahami Konsep Rekursi

👩‍🏫 Secara Formal:

Rekursi (Recursion) adalah sebuah teknik pemrograman di mana sebuah fungsi (atau *procedure*) memanggil dirinya sendiri untuk menyelesaikan sub-masalah yang lebih kecil. Agar tidak terjadi perulangan tak hingga (*infinite loop*), sebuah fungsi rekursif wajib memiliki Base Case (kondisi berhenti) dan Recurrence Relation (langkah rekursif yang menuju ke base case).

Analogi Jaman Now

Bayangin kamu dikasih kado Boneka Matryoshka (boneka Rusia yang berlapis-lapis). Kamu disuruh mencari sebuah cincin kecil di dalamnya.

  • Langkahmu: Buka boneka. Kalau di dalamnya ada cincin, Selesai! (Ini namanya Base Case).
  • Kalau di dalamnya ada boneka yang lebih kecil, kamu ulangi langkah yang sama: Buka boneka itu lagi! (Ini namanya Recursive Step).

Fungsi rekursif juga begitu, dia akan terus "membuka" tugas yang makin kecil sampai dia ketemu jawaban pastinya, lalu bawa jawabannya naik lagi ke atas!

Base Case

Kondisi paling sederhana yang nilainya sudah diketahui langsung tanpa harus memanggil fungsi rekursif lagi. Berfungsi untuk menghentikan rekursi.

Recurrence Relation

Aturan yang mengubah masalah besar menjadi masalah yang lebih kecil, dan diteruskan dengan memanggil fungsi itu sendiri lagi.

⚠️ Common Mistakes di OSN

  • Missing Base Case: Lupa memberikan kondisi berhenti, mengakibatkan Stack Overflow (program crash karena memori penuh).
  • Salah Menempatkan Base Case: Menaruh base case di bawah recursive call. Base case harus selalu ditaruh di awal fungsi sebelum rekursi memanggil kembali.
  • Lupa return: Pada fungsi yang mengembalikan nilai, lupa menulis return saat memanggil fungsi rekursif, sehingga hasil perhitungan dari fungsi anak tidak tersampaikan ke fungsi pemanggilnya.

Animasi: Call Stack & Rekursi

Ketika fungsi memanggil dirinya sendiri, komputer menggunakan memori bernama Stack untuk menumpuk tugas (*Call Stack*). Perhatikan animasi hitungMundur(3) di bawah ini! 

void hitungMundur(int n) {
  if (n == 0) {
    cout << "Selesai!";
    return; // Base case
  }
  cout << n << " ";
  hitungMundur(n - 1); // Rekursi
}
Call Stack Memory
Status: Paused

Lab: Simulator Tracing Faktorial

Berbeda dengan prosedur hitungMundur yang tidak mengembalikan nilai (void), fungsi matematika seperti Faktorial (N!) mengembalikan nilai (return) yang harus ditangkap oleh si pemanggil di dalam stack saat dia turun / selesai. Coba jalankan step-by-step!

C++
int faktorial(int N) {
  if (N == 1)
    return 1;
  else
    return N * faktorial(N - 1);
}

int main() {
  int hasil = faktorial(3);
}
Call Stack & Variabel
State Saat Ini:
Klik 'Next Step' untuk memulai di fungsi main().
Return Value:
-

Question Card

Apa yang akan terjadi pada memori komputer jika kita lupa membuat Base Case pada fungsi rekursif?

⚠️ Common Mistakes: Pass by Value vs Reference

Saat melakukan rekursi mendalam (seperti Backtracking atau DFS) dengan tipe data berat (seperti vector atau string di C++), hindari mem-passing parameter secara Value.

Solusi: Gunakan Pass-by-Reference (vector<int>& arr) agar array tidak di-copy berulang kali di memori setiap kali fungsi dipanggil, yang dapat memicu Time Limit Exceeded (TLE) atau Memory Limit Exceeded (MLE).

Modul Rekursi Selesai!
Kerjakan Kuis OSN